{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2**\n",
    "\n",
    "**120**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-------------------\n",
    "# 2. 两数相加(未完成)\n",
    "-------------------\n",
    "给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。\n",
    "\n",
    "* 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。\n",
    "\n",
    "* **示例：\n",
    "\n",
    "    * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)\n",
    "    * 输出：7 -> 0 -> 8\n",
    "    * 原因：342 + 465 = 807"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----------------------------------------------\n",
    "## 涉及内容:\n",
    " * 1. 链表的基本应用\n",
    "----------------------------------------------\n",
    "## 难点：\n",
    " * 1. 关于链表长度不同\n",
    "     * l1.len!=l2.len: 注意处理较长链表的剩余部分\n",
    " * 2. 关于计算\n",
    "     * 需加入进位　carry"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = (int)(x)\n",
    "        self.next = None\n",
    "    def inits(l):\n",
    "        head = l\n",
    "        val = 0\n",
    "        while True:\n",
    "            val = input()\n",
    "            if val == '#':\n",
    "                l=None\n",
    "                break\n",
    "            l.val = (int)(val)\n",
    "            l.next = ListNode(0)\n",
    "            l = l.next\n",
    "        return head    \n",
    "    def init(l):\n",
    "        head = l\n",
    "        val = 0\n",
    "        flag=False\n",
    "        while True:\n",
    "            val = input()\n",
    "            if val == '#':\n",
    "                l=None\n",
    "                break\n",
    "            else:\n",
    "                if flag:\n",
    "                    l = ListNode(0) \n",
    "                else:\n",
    "                    flag = True\n",
    "            l.val = (int)(val)\n",
    "            l = l.next\n",
    "        return head   \n",
    "    def __str__(self):\n",
    "        while(self!=None):\n",
    "            print(self.val)\n",
    "            self=self.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        head = ListNode(0)\n",
    "        result = head\n",
    "        index = 0\n",
    "        flag = 0\n",
    "        while l1!=None or l2!=None:\n",
    "            dim = (l1.val+l2.val)%10\n",
    "            result.val = dim+flag\n",
    "            flag = (l1.val+l2.val)//10\n",
    "            result.next = ListNode(0)\n",
    "            result = result.next\n",
    "        heads = head\n",
    "        while head.next!=None:\n",
    "            print(head.val)\n",
    "            head = head.next\n",
    "        return heads\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = ListNode(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "#\n"
     ]
    }
   ],
   "source": [
    "l = ListNode.init(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "Solution.show(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "__str__ returned non-string (type NoneType)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-51-e6f469464218>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: __str__ returned non-string (type NoneType)"
     ]
    }
   ],
   "source": [
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "l.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = (int)(x)\n",
    "        self.next = None\n",
    "    def init(l):\n",
    "        head = l\n",
    "        val = 0\n",
    "        while True:\n",
    "            val = input()\n",
    "            if val == '#':\n",
    "                break\n",
    "            l.val = (int)(val)\n",
    "            print(l.val)\n",
    "            l.next = ListNode(0)\n",
    "            l = l.next\n",
    "        return head\n",
    "    def show(l):\n",
    "        while l != None:\n",
    "            print(l.val)\n",
    "            l = l.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = ListNode(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "head = l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        head = ListNode(0)\n",
    "        result = head\n",
    "        index = 0\n",
    "        flag = 0\n",
    "        while l1!=None or l2!=None:\n",
    "            dim = (l1.val+l2.val)%10\n",
    "            result.val = dim+flag\n",
    "            flag = (l1.val+l2.val)//10\n",
    "            result.next = ListNode(0)\n",
    "            result = result.next\n",
    "        heads = head\n",
    "        while head.next!=None:\n",
    "            print(head.val)\n",
    "            head = head.next\n",
    "        return heads"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "3\n",
      "2\n",
      "2\n",
      "1\n",
      "1\n",
      "#\n"
     ]
    }
   ],
   "source": [
    "l = ListNode.init(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "ListNode.print_list(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'val'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-13-747eb7a9da4d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0ml\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'val'"
     ]
    }
   ],
   "source": [
    "l.next.val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 88. Merge Sorted Array\n",
    "#### Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.\n",
    "\n",
    "* Note:\n",
    "\n",
    "    * The number of elements initialized in nums1 and nums2 are m and n respectively.\n",
    "    * You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.\n",
    "\n",
    "* Example:\n",
    "\n",
    "    * Input:\n",
    "    * nums1 = [1,2,3,0,0,0], m = 3\n",
    "    * nums2 = [2,5,6],       n = 3\n",
    "    * Output: [1,2,2,3,5,6]\n",
    " \n",
    "\n",
    "* Constraints:\n",
    "\n",
    "    * -10^9 <= nums1[i], nums2[i] <= 10^9\n",
    "    * nums1.length == m + n\n",
    "    * nums2.length == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(num_list_1,m,num_list_2,n):\n",
    "       def exchange(num_list,p1,p2):\n",
    "            num_list[p1], num_list[p2] = num_list[p2], num_list[p1]\n",
    "            p1-=1\n",
    "            p2-=1\n",
    "            return num_list, p1, p2\n",
    "        if m==0:\n",
    "            for i in range(n):\n",
    "                num_list_1[i] = num_list_2[i]\n",
    "            return;\n",
    "        for i in range(n):\n",
    "            num_list_1[m+i] = num_list_2[i]\n",
    "        for i in range(0,n):\n",
    "            p2 = m+i\n",
    "            p1 = p2-1\n",
    "            while(num_list_1[p2]<=num_list_1[p1] \n",
    "              and max(p1,p2)<(m+n) and min(p1,p2)>=0):\n",
    "                num_list_1,p1,p2 = exchange(num_list_1,p1,p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -- 1\n"
     ]
    }
   ],
   "source": [
    "la = [2,0]\n",
    "lb = [1]\n",
    "merge(la,1,lb,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "la"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 119. Pascal's Triangle II(已完成)\n",
    "\n",
    "#### Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.\n",
    "\n",
    "#### Note that the row index starts from 0.\n",
    "\n",
    "\n",
    "#### In Pascal's triangle, each number is the sum of the two numbers directly above it.\n",
    "\n",
    "* Example:\n",
    "\n",
    "    * Input: 3\n",
    "    * Output: [1,3,3,1]\n",
    "* Follow up:\n",
    "    * Could you optimize your algorithm to use only O(k) extra space?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Pascal(line_num):\n",
    "    Pascal_list = [[]]*line_num\n",
    "    print(len(Pascal_list))\n",
    "    for i in range(0,line_num):\n",
    "        \n",
    "        Pascal_list[i] = [(int)(0)]*(i+1)  # 若从0开始记，第i行有（i+1）个元素，首先初始化为0\n",
    "        Pascal_list[i][0] = 1\n",
    "        if (i==0) :\n",
    "            continue    # 第一行只有1个元素，不必往下运行\n",
    "        Pascal_list[i][i] = 1  # 将首位和末位置1\n",
    "        for j in range(1,i):\n",
    "            Pascal_list[i][j] = Pascal_list[i-1][j-1] + Pascal_list[i-1][j]\n",
    "    return Pascal_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def show_Pascal(Pascal):\n",
    "    for i in range(len(Pascal)):\n",
    "        for j in range(len(Pascal[i])):\n",
    "            print(Pascal[i][j],end=' ')\n",
    "        print('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "test = Pascal(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1 1"
     ]
    }
   ],
   "source": [
    "show_Pascal(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[1, 1]\n",
      "[1, 2, 1]\n",
      "[1, 3, 3, 1]\n",
      "[1, 4, 6, 4, 1]\n",
      "[1, 5, 10, 10, 5, 1]\n",
      "[1, 6, 15, 20, 15, 6, 1]\n"
     ]
    }
   ],
   "source": [
    "for i in test:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [1, 1]]\n"
     ]
    }
   ],
   "source": [
    "print(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name '__main__' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-26-d06307706777>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     39\u001b[0m     \u001b[0mPascal_list\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mPascal\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mline_num\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     40\u001b[0m     \u001b[0mshow_Pascal\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mPascal_list\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 41\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0m__name__\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0m__main__\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     42\u001b[0m     \u001b[0mmain\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name '__main__' is not defined"
     ]
    }
   ],
   "source": [
    "def Pascal(line_num):\n",
    "    Pascal_list = [[]]*line_num\n",
    "    print(len(Pascal_list))\n",
    "    for i in range(0,line_num):\n",
    "        \n",
    "        Pascal_list[i] = [(int)(0)]*(i+1)  # 若从0开始记，第i行有（i+1）个元素，首先初始化为0\n",
    "        Pascal_list[i][0] = 1\n",
    "        if (i==0) :\n",
    "            continue    # 第一行只有1个元素，不必往下运行\n",
    "        Pascal_list[i][i] = 1  # 将首位和末位置1\n",
    "        for j in range(1,i):\n",
    "            Pascal_list[i][j] = Pascal_list[i-1][j-1] + Pascal_list[i-1][j]\n",
    "    return Pascal_list\n",
    "\n",
    "def normal_print(data):\n",
    "    print(data, end=' ')\n",
    "\n",
    "def line_end_print(data):\n",
    "    print(data)\n",
    "def end_print(data):\n",
    "    print(data,end='')\n",
    "\n",
    "def print_data(Pascal_list,i,j):\n",
    "    if j == (len(Pascal_list[i])-1):  # 行末元素\n",
    "        if i == (len(Pascal_list)-1): # Pascal最末尾的元素\n",
    "            end_print(Pascal_list[i][j])\n",
    "        else:\n",
    "            line_end_print(Pascal_list[i][j])\n",
    "    else:\n",
    "        normal_print(Pascal_list[i][j])\n",
    "\n",
    "def show_Pascal(Pascal_list):\n",
    "    for i in range(len(Pascal_list)):\n",
    "        for j in range(len(Pascal_list[i])):\n",
    "            print_data(Pascal_list,i,j)\n",
    "\n",
    "# def main():\n",
    "#     line_num = input()\n",
    "#     Pascal_list = Pascal(line_num)\n",
    "#     show_Pascal(Pascal_list)\n",
    "# if __name__ == __main__:\n",
    "#     main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 120. 三角形最小路径和（未完成）\n",
    "给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。\n",
    "\n",
    "**相邻的结点** 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。\n",
    "\n",
    "例如，给定三角形：\n",
    "\n",
    "    [\n",
    "         [2],\n",
    "        [3,4],\n",
    "       [6,5,7],\n",
    "      [4,1,8,3]\n",
    "    ]\n",
    "自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。\n",
    "\n",
    " \n",
    "\n",
    "说明：\n",
    "\n",
    "如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "不能是贪心算法\n",
    "'''\n",
    "def minimumTotal(triangle_list):\n",
    "    sums = triangle_list[0][0]\n",
    "    print(sums)\n",
    "    index = 0\n",
    "    if len(triangle_list)>1:\n",
    "        for i in range(1,len(triangle_list)):\n",
    "            if(index<(len(triangle_list[i])-1)):\n",
    "                sums+=min(triangle_list[i][index],triangle_list[i][index+1])\n",
    "                print(sums,'____',index)\n",
    "                if(triangle_list[i][index]>triangle_list[i][index+1]):\n",
    "                    index+=1\n",
    "            else:\n",
    "                sums+=triangle_list[i][index]\n",
    "                print(sums,'____',index)\n",
    "    return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=[  [-1],\n",
    "     [2,3],\n",
    "   [1,-1,-3]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(1,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n",
      "1 ____ 0\n",
      "0 ____ 0\n"
     ]
    }
   ],
   "source": [
    "b = minimumTotal(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 344. Reverse String(已完成)\n",
    "\n",
    "* Write a function that reverses a string. The input string is given as an array of characters char[].\n",
    "\n",
    "* Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.\n",
    "\n",
    "* You may assume all the characters consist of printable ascii characters.\n",
    "\n",
    " \n",
    "\n",
    "* Example 1:\n",
    "\n",
    "    * Input: [\"h\",\"e\",\"l\",\"l\",\"o\"]\n",
    "    * Output: [\"o\",\"l\",\"l\",\"e\",\"h\"]\n",
    "* Example 2:\n",
    "\n",
    "    * Input: [\"H\",\"a\",\"n\",\"n\",\"a\",\"h\"]\n",
    "    * Output: [\"h\",\"a\",\"n\",\"n\",\"a\",\"H\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def reverse_string(str_list):\n",
    "        for i in range(len(str_list)//2):\n",
    "            str_list[i], str_list[len(str_list)-1-i] = str_list[len(str_list)-1-i], str_list[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = ['h','l','s']\n",
    "Solution.reverse_string(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['s', 'l', 'h']"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 350. 两个数组的交集 II\n",
    "\n",
    "**给定两个数组，编写一个函数来计算它们的交集。\n",
    "\n",
    "* 示例 1：\n",
    "\n",
    "    * 输入：nums1 = [1,2,2,1], nums2 = [2,2]\n",
    "    * 输出：[2,2]\n",
    "* 示例 2:\n",
    "\n",
    "    * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]\n",
    "    * 输出：[4,9]\n",
    " \n",
    "\n",
    "* 说明：\n",
    "\n",
    "    输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。我们可以不考虑输出结果的顺序。\n",
    "\n",
    "* 进阶：\n",
    "\n",
    "    * 如果给定的数组已经排好序呢？你将如何优化你的算法？\n",
    "    * 如果 nums1 的大小比 nums2 小很多，哪种方法更优？\n",
    "    * 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 空列表\n",
    "2. 元素过大"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-28-a0206e799abd>, line 6)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-28-a0206e799abd>\"\u001b[0;36m, line \u001b[0;32m6\u001b[0m\n\u001b[0;31m    long[] basket_1 = [0]*(max_-min_+1)\u001b[0m\n\u001b[0m         ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "def intersection(num_list_1,num_list_2):\n",
    "    min_1, max_1 = min(num_list_1), max(num_list_1)\n",
    "    min_2, max_2 = min(num_list_2), max(num_list_2)\n",
    "    min_ = min(min_1, min_2)\n",
    "    max_ = max(max_1, max_2)\n",
    "    basket_1 = [0]*(max_-min_+1)\n",
    "    basket_2 = [0]*(max_-min_+1)\n",
    "    intersection_list = []\n",
    "    for i in num_list_1:\n",
    "        basket_1[i-min_]+=1\n",
    "    for i in num_list_2:\n",
    "        #print(i,'----',min_)\n",
    "        basket_2[i-min_]+=1\n",
    "    for i in range(max(min_1, min_2), min(max_1,max_2)+1):\n",
    "        if basket_1[i-min_]!=0 and basket_2[i-min_]!=0:\n",
    "            for cnt in range(min(basket_1[i-min_], basket_2[i-min_])):\n",
    "                intersection_list.append(i)\n",
    "        '''\n",
    "            print(i-min_,'++')\n",
    "        else:\n",
    "            print(i-min_,'--')\n",
    "            print(basket_1[i-min_],'____',basket_2[i-min_])\n",
    "        '''\n",
    "    return intersection_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection(num_list_1, num_list_2):\n",
    "    basket_1 = [[0]]*(min(len(num_list_1, len(num_list_2))))\n",
    "    basket_2 = [[0]]*(min(len(num_list_1, len(num_list_2))))\n",
    "    intersection_list = []\n",
    "    for i in num_list_1:\n",
    "        basket_1[][0]+=1\n",
    "    for i in num_list_2:\n",
    "        basket_2[i][0]+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection(num_list_1, num_list_2):\n",
    "    intersection_list = []\n",
    "    for i in range (len(num_list_1)):\n",
    "        for j in range(len(num_list_2)):\n",
    "            if num_list_1[i] == num_list_2[j] and num_list_1[i] !=None and num_list_2[j]!=None:\n",
    "                intersection_list.append(num_list_1[i])\n",
    "                num_list_2[j]=num_list_1[i] = None\n",
    "    return intersection_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "la = [1,2,2,1,2]\n",
    "lb = [2,1,3,4,2]\n",
    "lc = intersection(la,lb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---------------------------------\n",
    "# 392. Is Subsequence \n",
    "---------------------------------\n",
    "Given a string s and a string t, check if s is subsequence of t.\n",
    "\n",
    "A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, \"ace\" is a subsequence of \"abcde\" while \"aec\" is not).\n",
    "\n",
    "* Follow up:\n",
    "    * If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?\n",
    "\n",
    "* Credits:\n",
    "    * Special thanks to @pbrother for adding this problem and creating all test cases.\n",
    "\n",
    " \n",
    "\n",
    "* Example 1:\n",
    "\n",
    "    Input: s = \"abc\", t = \"ahbgdc\"\n",
    "    Output: true\n",
    "* Example 2:\n",
    "\n",
    "    Input: s = \"axc\", t = \"ahbgdc\"\n",
    "    Output: false\n",
    " \n",
    "\n",
    "* Constraints:\n",
    "\n",
    "    * 0 <= s.length <= 100\n",
    "    * 0 <= t.length <= 10^4\n",
    " \n",
    " Both strings consists only of lowercase characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Subsequence(s,t):\n",
    "    index = 0\n",
    "    for i in range(len(t)):\n",
    "        if(t[i]==s[index]):\n",
    "            index+=1\n",
    "        if index==len(s):\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 922. Sort Array By Parity II\n",
    "* Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.\n",
    "  Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.\n",
    "\n",
    "You may return any answer array that satisfies this condition. \n",
    "\n",
    "* Example 1:\n",
    "\n",
    "    * Input: [4,2,5,7]\n",
    "    * Output: [4,5,2,7]\n",
    "    * Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.\n",
    "\n",
    "* Note:\n",
    "    * 2 <= A.length <= 20000\n",
    "    * A.length % 2 == 0\n",
    "    * 0 <= A[i] <= 1000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 922. 按奇偶排序数组 II\n",
    "\n",
    "* 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。\n",
    "  对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。\n",
    "\n",
    "你可以返回任何满足上述条件的数组作为答案。\n",
    "\n",
    "* 示例：\n",
    "\n",
    "    * 输入：[4,2,5,7]\n",
    "    * 输出：[4,5,2,7]\n",
    "    * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。\n",
    "* 提示：\n",
    "\n",
    "    * 2 <= A.length <= 20000\n",
    "    * A.length % 2 == 0\n",
    "    * 0 <= A[i] <= 1000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* ## 双指针\n",
    "* ## 排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "class odd_even_arr:\n",
    "    def soft_arr_by_parity(num_list):\n",
    "        '''\n",
    "        时间复杂度 O（N），空间复杂度O（N）\n",
    "        '''\n",
    "        odd_index = 1\n",
    "        even_index = 0\n",
    "        new_list = [0]*len(num_list)\n",
    "        for i in num_list:\n",
    "            if i%2==0:\n",
    "                new_list[even_index] = i\n",
    "                even_index+=2\n",
    "            else:\n",
    "                new_list[odd_index] = i\n",
    "                odd_index+=2\n",
    "        return new_list\n",
    "    def soft_arr_by_parity_2(A):\n",
    "        '''\n",
    "        时间复杂度O（N），空间复杂度O（1）\n",
    "        双指针\n",
    "        '''\n",
    "        odd_index = 1\n",
    "        for even_index in range(0, len(A), 2):\n",
    "            if A[even_index]%2==1:\n",
    "                while A[odd_index]%2==1:\n",
    "                    odd_index+=2\n",
    "                print(odd_index,'--',even_index)\n",
    "                A[even_index], A[odd_index] = A[odd_index], A[even_index]\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [4,2,7,9]\n",
    "a_2 = odd_even_arr.soft_arr_by_parity(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 7, 2, 9]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a_2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1370. Increasing Decreasing String\n",
    "* Given a string s. You should re-order the string using the following algorithm:\n",
    "\n",
    "    * Pick the smallest character from s and append it to the result.\n",
    "    * Pick the smallest character from s which is greater than the last appended character to the result and append it.\n",
    "    * Repeat step 2 until you cannot pick more characters.\n",
    "    * Pick the largest character from s and append it to the result.\n",
    "    * Pick the largest character from s which is smaller than the last appended character to the result and append it.\n",
    "    * Repeat step 5 until you cannot pick more characters.\n",
    "    * Repeat the steps from 1 to 6 until you pick all characters from s.\n",
    "\n",
    "In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.\n",
    "\n",
    "Return the result string after sorting s with this algorithm.\n",
    "\n",
    "* #### Example 1:\n",
    "\n",
    "    * Input: s = \"aaaabbbbcccc\"\n",
    "    * Output: \"abccbaabccba\"\n",
    "    * Explanation: After steps 1, 2 and 3 of the first iteration, result = \"abc\"\n",
    "    * After steps 4, 5 and 6 of the first iteration, result = \"abccba\", \n",
    "    * First iteration is done. Now s = \"aabbcc\" and we go back to step 1\n",
    "    * After steps 1, 2 and 3 of the second iteration, result = \"abccbaabc\"\n",
    "    * After steps 4, 5 and 6 of the second iteration, result = \"abccbaabccba\"\n",
    "\n",
    "* #### Example 2:\n",
    "\n",
    "    * Input: s = \"rat\"\n",
    "    * Output: \"art\"\n",
    "    * Explanation: The word \"rat\" becomes \"art\" after re-ordering it with the mentioned algorithm.\n",
    "\n",
    "* #### Example 3:\n",
    "\n",
    "    * Input: s = \"leetcode\"\n",
    "    * Output: \"cdelotee\"\n",
    "    \n",
    "* #### Example 4:\n",
    "\n",
    "    * Input: s = \"ggggggg\"\n",
    "    * Output: \"ggggggg\"\n",
    "\n",
    "* #### Example 5:\n",
    "\n",
    "    * Input: s = \"spo\"\n",
    "    * Output: \"ops\"\n",
    " \n",
    "* #### Constraints:\n",
    "\n",
    "    * 1 <= s.length <= 500\n",
    "    * s contains only lower-case English letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
